home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 11218 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.3 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: binary tree question
  5. Date: 22 Mar 1996 09:05:23 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4iumkjINNsp3@keats.ugrad.cs.ubc.ca>
  8. References: <4isglj$cgg@netaxs.com>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4isglj$cgg@netaxs.com>, J. A. McNamara <grulm@netaxs.com> wrote:
  12.  >I'm willing to bet that the answer to this is obvious, but I'm trying to 
  13.  >free each node of a binary tree as it is read -- preferably *after* it's
  14.  >been read :)  the following code doesn't appear to free the memory, but I 
  15.  >haven't figured out how to prod my debugger into telling me how much memory
  16.  >is being used, so I'm not so sure . . .  (by the way, it gives me no
  17.  >problems in any other respect).  (I'd also like to mention that this is 
  18.  >*not* homework)
  19.  >
  20.  >/***********************************************************************/
  21.  >/*link is the linked list struct type; tree_n is the tree node struct type*/
  22.  >/* addlink() works fine, too, and both are prototyped. */
  23.  >
  24.  >link *inorder(tree_n *tn, link *tail, int *i)   /* read tree into list */
  25.  >    {
  26.  >        if (tn != NULL) {
  27.  >            tail = inorder(tn->l, tail, i);
  28.  >            tail = addlink(tail, tn->f);      /* hand data ptr to list */
  29.  >            (*i)++;                           /* keep track of total   */
  30.  >            tail = inorder(tn->r, tail, i);
  31.  >        }
  32.  >        if (tn!=NULL) free(tn); tn=NULL;
  33.  >        return tail;
  34.  >    }
  35.  >/**************************************************************************/
  36.  
  37. This is not a pure ``inorder'' traversal. The nodes are being added to the
  38. linked list in order, but you are freeing in post-order (children are visited
  39. first, then you free the parent).
  40.  
  41. Why don't you combine the two if() statements into one? They have precisely the
  42. same expression, and tn is never assigned to in the body of the first one, so
  43. the evaluation of the expression doesn't change.
  44.  
  45. You do not need to assign NULL to the ``tn'' pointer after you have invoked
  46. free() on it. This is a waste of time, since it has been passed to the
  47. procedure by value. You are only affecting the value of the function parameter
  48. ``tn'', not any external object. This value is never used, so the compiler will
  49. throw that assignment away at the optimization phase.
  50.  
  51.  >I also tried the following:
  52.  >
  53.  >free(tn->l); tn->l=NULL;
  54.  >free(tn->r); tn->r=NULL;
  55.  >
  56.  >. . .  which gave me some serious garbage, though I'm not quite sure why.
  57.  
  58. Because you probably did not check whether the children are null pointers or
  59. not, only whether tn is a null pointer. Just because tn is a valid tree node
  60. doesn't mean that tn->l or tn->r are. The above modification will also fail to
  61. free the root node.
  62.  
  63.  >any help would be appreciated.  thanks in advance.
  64.  
  65. Your code appears fine. That it's not actually freeing memory is not
  66. surprising. Many free() implementations don't free memory, they only return
  67. free blocks to a list from where subsequent malloc() invocations can obtain
  68. memory quickly.
  69.  
  70. Exception: on some UNIX systems, there is a special malloc() implementation
  71. which will use what are called memory mapped regions for very large blocks
  72. (like if you malloc ten megabytes, say), and these *are*, fortunately, returned
  73. to the system when you call free()!
  74. -- 
  75.  
  76.